"""
Problem 86: https://projecteuler.net/problem=86

某蜘蛛S在一长方体的一角上, 这个长方体的长宽高分别是6、5、3, 在长方体的对角上还有一只苍蝇F。
从S至F的最智短「直线」距离是10, 路径如图所示:


然而，实际上对于任何长方体, 像这样的「最短」路径往往可以达到3种, 并且最短路径的长不一定是整数。

假设长方体的长宽高的值都是整数且最大不超过整数M, 那么当M=100时就有2060种长方体的如上「最短路径」的长是整数,
而这个M的值也是使这种长方体的种数超过2000的最小值。当M=99时这样的长方体有1975种。

请找到最小的M, 使得这样的长方体种数超过100,0000。
"""


MAX_M = 2000
n_pow2 = {n: n*n for n in range(2*MAX_M)}
# print('n_pow2 is OK!')


def minpathAD(a: int, d: int) -> float:
    '''
    assume  d = b+c  (a >= b >= c)
    >>> assert minpathAD(6,8) == 10
    '''
    def np2(n): return n_pow2[n] if n in n_pow2 else n*n

    return (np2(a)+np2(d))**0.5


MDict = dict()  # {a : b_c_combins}


def MDictGen(maxM: int):
    '''
    count (a,b,c) where M >= a >= b >= c and minpathABC(a,b,c)  is int
    '''
    for a in range(maxM+1):
        MDict[a] = 0
        for d in range(2, 2*a+1):
            mp = minpathAD(a, d)
            if mp == int(mp):
                MDict[a] += sum(1 for b in range(1, a+1) if 1 <= d-b <= b)


MDictGen(MAX_M)
# print(sum(MDict[i] for i in range(100))) # == 1975
# print(sum(MDict[i] for i in range(101))) # == 2060
# print('MDict is(2000) OK!')


def solution(limit: int = 1000000) -> int:
    MDict_sum = {0: 0}
    for m in range(1, len(MDict)):
        MDict_sum[m] = MDict_sum[m-1] + MDict[m]
        if MDict_sum[m-1] <= limit and MDict_sum[m] > limit:
            return m


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 1818
